Finding Critical Nodes for Inhibiting Diffusion of Complex Contagions in Social Networks.

Algorithms for compressing GPS trajectory data an empirical evaluation.

A SAT%2Dbased Framework for Efficient Constrained Clustering.

Topology control in constant rate mobile ad hoc networks.
Topology control is the problem of assigning power levels to the nodes of an ad hoc network so as to create a specified network topology while minimizing the energy consumed by the network nodes. While considerable theoretical attention has been given to the issue of topology control in wireless ad hoc networks, all of that prior work has concerned stationary networks. When the nodes are mobile, there is no algorithm that can guarantee a graph property (such as network connectivity) throughout the node movement. In this paper we study topology control in mobile wireless ad hoc networks (MANETs). We define a mobility model, namely the constant rate mobile network model (CRMN), in which we assume that the speed and direction of each moving node are known. The goal of topology control under this model is to minimize the maximum power used by any network node in maintaining a specified monotone graph property. Network connectivity is one of the most fundamental monotone properties. Under the CRMN model, we develop general frameworks for solving both the decision version (i.e. for a given value p&gt; 0, will a specified monotone property hold for the network induced by assigning the power value p to every node?) and the optimization version (i.e. find the minimum value p such that the specified monotone property holds for the network induced by assigning the power value p to every node) of the topology control problems. Efficient 1Preliminary results regarding connectivity only were presented at the GLOBECOM’06-WirelessComm [22] conference
Bi%2DCriteria Approximation Algorithms for Power%2DEfficient and Low%2DInterference Topology Control in Unreliable Ad Hoc Networks.
Abstract—Topology control in ad hoc networks is a multicriteria optimization problem involving (contradictory) objectives of connectivity, interference, and power minimization. Additionally, nodes can be unreliable, which adds another dimension to an already challenging problem. In this paper, we study topology control problems in ad hoc networks under node failures for arbitrary node distributions. We consider a simple and natural stochastic failure model, in which each node can fail independently with a given probability. The Topology Control Problem Under Stochastic Failures is to choose a power level for each node and a subset of edges such that the residual graph (i.e., the graph formed by the nodes which have not failed) is connected and can be scheduled efficiently, with high probability. We develop provably efficient bi-criteria approximation algorithms for this problem that simultaneously minimize power, reduce interference, and ensure that the surviving graph is connected with high probability. Our algorithms can be implemented efficiently in a distributed manner. A. Overview I.
Agent Based Modeling%2C Mathematical Formalism for.

Using instance%2Dlevel constraints in agglomerative hierarchical clustering theoretical and empirical results.

Using instance%2Dlevel constraints in agglomerative hierarchical clustering theoretical and empirical results.

Resilience Metrics for Service%2DOriented Networks A Service Allocation Approach.

Adversarial Scheduling Analysis of Game%2DTheoretic Models of Norm Diffusion.

A mathematical formalism for agent%2Dbased modeling

Adversarial Scheduling Analysis of Game Theoretic Models of Norm Diffusion

Adversarial Scheduling Analysis of Game Theoretic Models of Norm Diffusion



Guest editors%27 introduction.

Errata for the paper %22Predecessor existence problems for finite discrete dynamical systems%22 %5BTCS 386 %281%2D2%29 %282007%29 3%2D37%5D.


Intractability and clustering with constraints.


Efficient incremental constrained clustering.
Clustering with constraints is an emerging area of data mining research. However, most work assumes that the constraints are given as one large batch. In this paper we explore the situation where the constraints are incrementally given. In this way the user after seeing a clustering can provide positive and negative feedback via constraints to critique a clustering solution. We consider the problem of efficiently updating a clustering to satisfy the new and old constraints rather than re-clustering the entire data set. We show that the problem of incremental clustering under constraints is NP-hard in general, but identify several sufficient conditions which lead to efficiently solvable versions. These translate into a set of rules on the types of constraints that can be added and constraint set properties that must be maintained. We demonstrate that this approach is more efficient than re-clustering the entire data set and has several other advantages.
Complexity of Scheduling in Synthesizing Hardware from Concurrent Action Oriented Specifications.

The complexity of non%2Dhierarchical clustering with instance and cluster level constraints.

Predecessor existence problems for finite discrete dynamical systems.

Ad%2DHoc
hybrid cellular ad-hoc networks, security, routing protocols While wireless networking seems to be the way of the future, no definite architecture for large scale deployment of such networks has emerged. This can be attributed to financial reasons (a specialized infrastructure is too expensive to build) as well as to the lack of solutions that could work with an existing infrastructure or, in an ad hoc manner, without one. A viable alternative seems to be hybrid wireless networks. Such networks use the existing cellular telephony infrastructure as basis and enhance it by building ad hoc networks of traffic relayers around each cell, improving the overall throughtput and reliability of the network. These relayers are users of the network that are willing to operate as such. In this setting, both efficiency and security are vital properties. We propose SCP as an integrated solution for secure routing and crediting in hybrid networks. We describe how a secure environment can be established efficiently by financially motivating users to avoid attacks. Finally, we show that SCP imposes minimal load both in communication and computation, so that even regular cellular phones can function as relayers, without demanding infrastructure upgrades. 1
Identifying and Generating Easy Sets of Constraints for Clustering.

Topology Control for Constant Rate Mobile Networks.
Topology control is the problem of assigning power levels to the nodes of an ad hoc network so as to create a specified network topology while minimizing the energy consumed by the network nodes. While considerable theoretical attention has been given to the issue of topology control in wireless ad hoc networks, all of that prior work has concerned stationary networks. When the nodes are mobile, there is no algorithm that can guarantee a graph property (such as network connectivity) throughout the node movement. In this paper we study topology control in mobile wireless ad hoc networks (MANETs). We define a mobility model, namely the constant rate mobile network model (CRMN), in which we assume that the speed and direction of each moving node are known. The goal of topology control under this model is to minimize the maximum power used by any network node in maintaining a specified monotone graph property. Network connectivity is one of the most fundamental monotone properties. Under the CRMN model, we develop general frameworks for solving both the decision version (i.e. for a given value p&gt; 0, will a specified monotone property hold for the network induced by assigning the power value p to every node?) and the optimization version (i.e. find the minimum value p such that the specified monotone property holds for the network induced by assigning the power value p to every node) of the topology control problems. Efficient 1Preliminary results regarding connectivity only were presented at the GLOBECOM’06-WirelessComm [22] conference
Topology Control for Simple Mobile Networks.

Complexity of reachability problems for finite discrete dynamical systems.

Approximating the Minimum Number of Maximum Power Users in Ad hoc Networks.
Abstract. Topology control is the problem of assigning transmission power values to the nodes of an ad hoc network so that the induced graph satisfies some specified property. The most fundamental such property is that the network/graph be connected. For connectivity, prior work on topology control gave a polynomial time algorithm for minimizing the maximum power assigned to any node (such that the induced graph is connected). In this paper we study the problem of minimizing the number of maximum power nodes. After establishing that this minimization problem is NP-Complete, we focus on approximation algorithms for graphs with symmetric power thresholds. We first show that the problem is reducible in an approximation preserving manner to the problem of assigning power values so that the sum of the powers is minimized. Using known results for that problem, this provides a family of approximation algorithms for the problem of minimizing the number of maximum power nodes with approximation ratios of 5/3 +ɛ for every ɛ&gt;0. Unfortunately, these algorithms, based on solving large linear programming problems are not practical. The main result of this paper is a practical algorithm having a 5/3 (exactly) approximation ratio. In addition, we present experimental results on randomly generated networks. Finally, based on the reduction to minimizing the total power problem, we outline some additional results for minimizing the number of maximum power users, both for graph properties other than connectivity and for graphs with asymmetric power thresholds. 1
Obtaining online approximation algorithms for facility dispersion from offline algorithms.

Structure%2DBased Resilience Metrics for Service%2DOriented Networks.

Agglomerative Hierarchical Clustering with Constraints Theoretical and Empirical Results.
Abstract. We explore the use of instance and cluster-level constraints with agglomerative hierarchical clustering. Though previous work has illustrated the benefits of using constraints for non-hierarchical clustering, their application to hierarchical clustering is not straight-forward for two primary reasons. First, some constraint combinations make the feasibility problem (Does there exist a single feasible solution?) NP-complete. Second, some constraint combinations when used with traditional agglomerative algorithms can cause the dendrogram to stop prematurely in a dead-end solution even though there exist other feasible solutions with a significantly smaller number of clusters. When constraints lead to efficiently solvable feasibility problems and standard agglomerative algorithms do not give rise to dead-end solutions, we empirically illustrate the benefits of using constraints to improve cluster purity and average distortion. Furthermore, we introduce the new γ constraint and use it in conjunction with the triangle inequality to considerably improve the efficiency of agglomerative clustering. 1
Clustering with Constraints Feasibility Issues and the k%2DMeans Algorithm.
Recent work has looked at extending the k-Means algorithm to incorporate background information in the form of instance level must-link and cannot-link constraints. We introduce two ways of specifying additional background information in the form of # and # constraints that operate on all instances but which can be interpreted as conjunctions or disjunctions of instance level constraints and hence are easy to implement. We present complexity results for the feasibility of clustering under each type of constraint individually and several types together. A key finding is that determining whether there is a feasible solution satisfying all constraints is, in general, NP-complete. Thus, an iterative algorithm such as k-Means should not try to find a feasible partitioning at each iteration. This motivates our derivation of a new version of the k-Means algorithm that minimizes the constrained vector quantization error  but at each iteration does not attempt to satisfy all constraints. Using standard UCI datasets, we find that using constraints improves accuracy as others have reported, but we also show that our algorithm reduces the number of iterations until convergence. Finally, we illustrate these benefits and our new constraint types on a complex real world object identification problem using the infra-red detector on an Aibo robot.
Guest Editors%27 Introduction.

Algorithmic Aspects of Topology Control Problems for Ad Hoc Networks.
Topology control problems are concerned with the assignment of power values to the nodes of an ad~hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be NP-complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is obtained. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented.
Algorithmic Aspects of Topology Control Problems for Ad Hoc Networks.
Topology control problems are concerned with the assignment of power values to the nodes of an ad~hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be NP-complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is obtained. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented.
Approximating the Minimum Number of Maximum Power Users in Ad Hoc Networks.
Abstract. Topology control is the problem of assigning transmission power values to the nodes of an ad hoc network so that the induced graph satisfies some specified property. The most fundamental such property is that the network/graph be connected. For connectivity, prior work on topology control gave a polynomial time algorithm for minimizing the maximum power assigned to any node (such that the induced graph is connected). In this paper we study the problem of minimizing the number of maximum power nodes. After establishing that this minimization problem is NP-Complete, we focus on approximation algorithms for graphs with symmetric power thresholds. We first show that the problem is reducible in an approximation preserving manner to the problem of assigning power values so that the sum of the powers is minimized. Using known results for that problem, this provides a family of approximation algorithms for the problem of minimizing the number of maximum power nodes with approximation ratios of 5/3 +ɛ for every ɛ&gt;0. Unfortunately, these algorithms, based on solving large linear programming problems are not practical. The main result of this paper is a practical algorithm having a 5/3 (exactly) approximation ratio. In addition, we present experimental results on randomly generated networks. Finally, based on the reduction to minimizing the total power problem, we outline some additional results for minimizing the number of maximum power users, both for graph properties other than connectivity and for graphs with asymmetric power thresholds. 1
Local base station assignment with time intervals in mobile computing environments.

A mobility and traffic generation framework for modeling and simulating ad hoc communication networks.

Topology Control Problems under Symmetric and Asymmetric Power Thresholds.
Abstract. We consider topology control problems where the goal is to assign transmission powers to the nodes of an ad hoc network so as to induce graphs satisfying specific properties. The properties considered are connectivity, bounded diameter and minimum node degree. The optimization objective is to minimize the total power assigned to nodes. As these problems are NP-hard in general, our focus is on developing approximation algorithms with provable performance guarantees. We present results under both symmetric and asymmetric power threshold models. 1
Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.
3 Part of the work was done while the authors were visiting the Basic and Applied Simulation Sciences Group (NISAC)
Reachability problems for sequential dynamical systems with threshold functions.
A sequential dynamical system (SDS) over a domain § is a triple ¨�©��������� � , where (i) ©�¨������� � is an undirected graph with � nodes with each node having a state value from §, (ii) ������ �  ¤ �� �  ¦ �������������� � is a set of local transition functions with �� � denoting the local transition function associated with node �  � and (iii)  � is a permutation of (i.e., a total order on) the nodes in �. A single SDS transition is obtained by updating the states of the nodes in � by evaluating the function associated with each of them in the order given by �. We consider reachability problems for SDSs with restricted local transition functions. Our main intractability results show that the reachability problems for SDSs are PSPACEcomplete when either of the following restrictions hold: (i)  � consists of both simplethreshold-functions and simple-inverted-threshold functions, or (ii)  � consists only of thresholdfunctions that use weights in an asymmetric manner. Moreover, the results hold even for SDSs whose underlying graphs have bounded node degree and bounded pathwidth. Our lower bound results also extend to reachability problems for Hopfield networks and communicating finite state machines. On the positive side, we show that when � consists only of threshold functions that use weights in a symmetric manner, reachability problems can be solved efficiently provided all the weights are strictly positive and the ratio of the largest to the smallest weight is bounded by a polynomial function of the number of nodes.
Algorithmic aspects of topology control problems for ad hoc networks.
Topology control problems are concerned with the assignment of power values to the nodes of an ad~hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be NP-complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is obtained. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented.
A mobility and traffic generation framework for modeling and simulating ad hoc communication networks.

Budgeted Maximum Graph Coverage.
An instance of the maximum coverage problem is given by a  set of weighted ground elements and a cost weighted family of subsets  of the ground element set. The goal is to select a subfamily of total cost  of at most that of a given budget maximizing the weight of the covered  elements.
Parallel Approximation Schemes for a Class of Planar and Near Planar Combinatorial Optimization Problems.

Gardens of Eden and Fixed Points in Sequential Dynamical Systems.

Analysis Problems for Sequential Dynamical Systems and Communicating State Machines.


Adversarial models in evolutionary game dynamics.

Efficient Construction of Minimum Makespan Schedules for Tasks with a Fixed Number of Distinct Execution Times.


Upgrading bottleneck constrained forests.

Models and Approximation Algorithms for Channel Assignment in Radio Networks.
this paper, we consider the channel assignment problem for transmitters. The transmission of a station T is intended for and must be received collision-free by all the neighbors of T (i.e., the receivers which are within the range of T ). As pointed out in [25], only primary interference can arise in this situation. Thus, two stations cannot be assigned the same time slot if one station is within the range of the other or the two stations have a common neighbor (i.e., another station located in the intersection of the ranges of the two stations). The objective of the channel assignment problem is to allow the transceivers to communicate with each other without interference while using a minimum number of channels
Approximation Algorithms for Clustering to Minimize the Sum of Diameters.
. We consider the problem of partitioning the nodes of a complete  edge weighted graph into k clusters so as to minimize the sum  of the diameters of the clusters. Since the problem is NP-complete, our  focus is on the development of good approximation algorithms. When  edge weights satisfy the triangle inequality, we present the first approximation  algorithm for the problem. The approximation algorithm yields  a solution that has no more than 10k clusters such that the total diameter  of these clusters is within a factor O(log (n=k)) of the optimal value  for k clusters, where n is the number of nodes in the complete graph.  For any fixed k, we present an approximation algorithm that produces k  clusters whose total diameter is at most twice the optimal value. When  the distances are not required to satisfy the triangle inequality, we show  that, unless P = NP, for any ae  1, there is no polynomial time approximation  algorithm that can provide a performance guarantee of ae even  whe...
Algorithms for Path%2DBased Placement of Inspection Stations on Networks.

Facility Dispersion Problems Under Capacity and Cost Constraints.

Approximation Algorithms for Clustering to Minimize the Sum of Diameters.
. We consider the problem of partitioning the nodes of a complete  edge weighted graph into k clusters so as to minimize the sum  of the diameters of the clusters. Since the problem is NP-complete, our  focus is on the development of good approximation algorithms. When  edge weights satisfy the triangle inequality, we present the first approximation  algorithm for the problem. The approximation algorithm yields  a solution that has no more than 10k clusters such that the total diameter  of these clusters is within a factor O(log (n=k)) of the optimal value  for k clusters, where n is the number of nodes in the complete graph.  For any fixed k, we present an approximation algorithm that produces k  clusters whose total diameter is at most twice the optimal value. When  the distances are not required to satisfy the triangle inequality, we show  that, unless P = NP, for any ae  1, there is no polynomial time approximation  algorithm that can provide a performance guarantee of ae even  whe...
Alarm placement in systems with fault propagation.
this paper, we consider systems that can be modeled as directed
Improving Minimum Cost Spanning Trees by Upgrading Nodes.
We study budget constrained network upgrading problems. We are given an undirected  edge weighted graph G = (V; E) where node v 2 V can be upgraded at a cost of c(v).  This upgrade reduces the weight of each edge incident on v. The goal is to find a minimum  cost set of nodes to be upgraded so that the resulting network has a minimum  spanning tree of weight no more than a given budget D. The results obtained in the  paper include the following:  1. On the positive side, we provide a polynomial time approximation algorithm for  the above upgrading problem when the difference between the maximum and  minimum edge weights is bounded by a polynomial in n, the number of nodes in  the graph. The solution produced by the algorithm satisfies the budget constraint,  and the cost of the upgrading set produced by the algorithm is O(log n) times the  minimum upgrading cost needed to obtain a spanning tree of weight at most D.  2. In contrast, we show that, unless NP ` DTIME(n  O(log log n)  ), th...
Using Data Flow Information to Obtain Efficient Check Sets for Algorithm%2DBased Fault Tolerance.

Improving Minimum Cost Spanning Trees by Upgrading Nodes.
We study budget constrained network upgrading problems. We are given an undirected  edge weighted graph G = (V; E) where node v 2 V can be upgraded at a cost of c(v).  This upgrade reduces the weight of each edge incident on v. The goal is to find a minimum  cost set of nodes to be upgraded so that the resulting network has a minimum  spanning tree of weight no more than a given budget D. The results obtained in the  paper include the following:  1. On the positive side, we provide a polynomial time approximation algorithm for  the above upgrading problem when the difference between the maximum and  minimum edge weights is bounded by a polynomial in n, the number of nodes in  the graph. The solution produced by the algorithm satisfies the budget constraint,  and the cost of the upgrading set produced by the algorithm is O(log n) times the  minimum upgrading cost needed to obtain a spanning tree of weight at most D.  2. In contrast, we show that, unless NP ` DTIME(n  O(log log n)  ), th...
Upgrading Bottleneck Constrained Forests.

Path problems in networks with vector%2Dvalued edge weights.

Improving Spanning Trees by Upgrading Nodes.
Id: upgrade.tex,v 2.2 1997#09#18 13:14:08 krumke Exp wirth  We study bottleneck constrained network upgrading problems.We are given an edge weighted graph G =#V;E# where node v 2 V can be upgraded at a cost of c#v#. This upgrade reduces the delayofeach link emanating from v. The goal is to #nd a minimum cost set of nodes to be upgraded so that the resulting network has a good performance. The performance is measured by the bottleneckweightof  a minimum spanning tree.  We give a polynomial time appoximation algorithm with logarithmic performance guarantee, which is tight within a small constant factor as shown by our hardness results.  Preprint submitted to Elsevier Preprint 24 September 1997 Key words:  NP-hardness,  Approximation Algorithms, Network Design,  Spanning-Tree.  1 Introduction  Several problems arising in areas such as communication networks can be expressed in the following general form: Enhance the performance of an underlying network by carrying out upgrades at certain ...
Upgrading Bottleneck Constrained Forests.

Bicriteria Network Design Problems
We study a general class of bicriteria network design problems. A generic problem in this  class is as follows: Given an undirected graph and two minimization objectives (under different  cost functions), with a budget specified on the first, find a subgraph from a given subgraph-class  that minimizes the second objective subject to the budget on the first. We consider three different  criteria - the total edge cost, the diameter and the maximum degree of the network. Here, we  present the first polynomial-time approximation algorithms for a large class of bicriteria network  design problems for the above mentioned criteria. The following general types of results are  presented.  First, we develop a framework for bicriteria problems and their approximations. Second,  when the two criteria are the same we present a &#034;black box&#034; parametric search technique. This  black box takes in as input an (approximation) algorithm for the unicriterion situation and generates  an approximation algorit...
NC%2DApproximation Schemes for NP%2D and PSPACE%2DHard Problems for Geometric Graphs.
We present NC approximation schemes for a number of graph problems when restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner. Our approximation schemes exhibit the same time versus performance trade-off as the best known approximation schemes for planar graphs. We also define the concept of -precision unit disk graphs and show that for such graphs the approximation schemes have a better time versus performance trade-off than the approximation schemes for arbitrary unit disk graphs. Moreover, compared to unit disk graphs, we show that for -precision unit disk graphs, many more graph problems have efficient approximation schemes.  Our NC approximation schemes can also be extended to obtain efficient NC approximation schemes for several PSPACE-hard problems on unit disk graphs specified using a restricted version of the hierarchical specification language of Bentley, Ottmann and Widmayer. The approximation schemes for hierarchically specified un...
Bicriteria Network Design Problems.
We study a general class of bicriteria network design problems. A generic problem in this  class is as follows: Given an undirected graph and two minimization objectives (under different  cost functions), with a budget specified on the first, find a subgraph from a given subgraph-class  that minimizes the second objective subject to the budget on the first. We consider three different  criteria - the total edge cost, the diameter and the maximum degree of the network. Here, we  present the first polynomial-time approximation algorithms for a large class of bicriteria network  design problems for the above mentioned criteria. The following general types of results are  presented.  First, we develop a framework for bicriteria problems and their approximations. Second,  when the two criteria are the same we present a &#034;black box&#034; parametric search technique. This  black box takes in as input an (approximation) algorithm for the unicriterion situation and generates  an approximation algorit...
Approximation Algorithms for Certain Network Improvement Problems.
. We study budget constrained network upgrading problems. Such problems aim at nding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an edge weighted graph G = (V; E), in the edge based upgrading model, it is assumed that each edge e of the given network also has an associated function ce (t) that species the cost of upgrading the edge by an amount t. A reduction strategy species for each edge e the amount by which the length `(e) is to be reduced. In the node based upgrading model, a node v can be upgraded at an expense of c(v). Such an upgrade reduces the delay of each edge incident on v. For a given budget B, the goal is to nd an improvement strategy such that the total cost of reduction is at most the given budget B and the cost of a subgraph (e.g. minimum spanning tree) under the modied edge lengths is the best over all possible strategies which obey the budget constraint.  After providing a brief overview of the...
Modifying Edges of a Network to Obtain Short Subgraphs.
This paper considers problems of the following type: We are given an edge weighted graph G = (V, E). It is assumed that each edge e of the given network has an associated function c_e that specifies the cost of shortening the edge by a given amount and that there is a budget B on the total reduction cost. The goal is to develop a reduction strategy satisfying the budget constraint so that the total length of a minimum spanning tree in the modified network is the smallest possible over all reduction strategies that obey the budget constraint. We show that in general the problem of computing an optimal reduction strategy for modifying the network as above is NP-hard even for simple classes of graphs and linear functions c_e. We present the first polynomial time approximation algorithms for the problem, where the cost functions c_e are allowed to be taken from a broad class of functions. We also present improved approximation algorithms for the class of treewidth-bounded graphs when the cost functions are linear...
Improving Spanning Trees by Upgrading Nodes.
Id: upgrade.tex,v 2.2 1997#09#18 13:14:08 krumke Exp wirth  We study bottleneck constrained network upgrading problems.We are given an edge weighted graph G =#V;E# where node v 2 V can be upgraded at a cost of c#v#. This upgrade reduces the delayofeach link emanating from v. The goal is to #nd a minimum cost set of nodes to be upgraded so that the resulting network has a good performance. The performance is measured by the bottleneckweightof  a minimum spanning tree.  We give a polynomial time appoximation algorithm with logarithmic performance guarantee, which is tight within a small constant factor as shown by our hardness results.  Preprint submitted to Elsevier Preprint 24 September 1997 Key words:  NP-hardness,  Approximation Algorithms, Network Design,  Spanning-Tree.  1 Introduction  Several problems arising in areas such as communication networks can be expressed in the following general form: Enhance the performance of an underlying network by carrying out upgrades at certain ...
Multi%2Dsite distributed database transactions utilizing deferred update.

Hierarchically Specified Unit Disk Graphs.
We characterize the complexity of a number of basic optimization problems for unit disk  graphs specified hierarchically as in [BOW83, LW87a, Le88, LW92]. Both PSPACE-hardness  results and polynomial time approximations are presented for most of the problems considered.  These problems include minimum vertex coloring, maximum independent set, minimum  clique cover, minimum dominating set and minimum independent dominating set. Each of our  PSPACE-hardness results holds, when the hierarchical specifications are 1-level restricted and  the graphs are specified hierarchically either as in [BOW83] or as in [LW92]. The hardness  results presented here significantly extend the hardness results in [BOW83, LW92]. The approximation  algorithms presented here along with our results in [MHR93, MHSR94] are among  the first polynomial time approximation algorithms for natural PSPACE-hard functions.  Classification: Succinct Specifications, Intersection Graphs, Approximation Algorithms, Computationa...
Compact Location Problems.
We consider the problem of placing a specified number (p) of facilities on the nodes  of a network so as to minimize some measure of the distances between facilities. This  type of problem models a number of problems arising in facility location, statistical clustering,  pattern recognition, and processor allocation problems in multiprocessor systems.  We consider the problem under three different objectives, namely minimizing the diameter,  minimizing the average distance, and minimizing the variance. We observe that in  general, the problem is NP-hard under any of the objectives. Further, even obtaining a  constant factor approximation for any of the objectives is NP-hard.  We present a general framework for obtaining near-optimal solutions to the compact  location problems for the above measures, when the distances satisfy the triangle  inequality. We show that this framework can be extended to the case when there are  also node weights. Further, we investigate the complexity and ap...
Deferred Updates and Data Placement in Distributed Databases.
Commercial distributed database systems generally support an optional protocol that provides loose consistency  of replicas, allowing replicas to be inconsistent for some time. In such a protocol, each replicated data item is assigned a primary copy site. Typically, a transaction updates only the primary copies of data items, with updates to other copies deferred until after the transaction commits. After a transaction commits, its updates to primary copies are sent transactionally to the other sites containing secondary copies. We investigate the transaction model underlying the above protocol. We show that global serializability in such a system is a property of the placement of primary and secondary copies of replicated data items. We present a polynomial time algorithm to assign primary sites to data items so that the resulting topology ensures serializability.   1 Introduction  A widely used method for improving the reliability and availability of data in distributed databases is ...

I%2FO Automata Based Verification of Finite State Distributed Systems Complexity Issues %28Abstract%29.

Modifying Networks to Obtain Low Cost Trees.
We consider the problem of reducing the edge lengths of a given network so that the modified network has a spanning tree of small total length. It is assumed that each edge e of the given network has an associated function Ce that specifies the cost of shortening the edge by a given amount and that there is a budget B  on the total reduction cost. The goal is to develop a reduction strategy satisfying the budget constraint so that the total length of a minimum spanning tree in the modified network is the smallest possible over all reduction strategies that obey the budget constraint. We show that in general the problem of computing optimal reduction strategy for modifying the network as above is NP-hard and present the first polynomial time approximation algorithms for the problem, where the cost functions Ce are allowed to be taken from a broad class of functions. We also present improved approximation algorithms for the class of treewidth-bounded graphs when the cost functions are li...
On Multi%2DLabel Linear Interval Routing Schemes.


On Approximation Algorithms for the Minimum Satisfiability Problem.
this paper, our focus is on deterministic approximation algorithms for the MINSAT problem. From now on, we will use the word `heuristic&#039; to mean a deterministic approximation algorithm which runs in polynomial time. Note that when the clauses are of size \Theta(n), where n is the number of variables, the heuristic analyzed in [18] provides only a weak performance guarantee of \Theta(n). We present a simple approximation-preserving reduction from MINSAT to the minimum vertex cover (MINVC) problem. This reduction, in conjunction with known heuristics for the MINVC problem (see for example, [8,22]), yields a heuristic with a performance guarantee of 2 for MINSAT, thus improving the result of Kohli et al. [18]. We also show that MINSAT is as hard to approximate as MINVC; that is, if there is a heuristic with a performance guarantee ae for MINSAT, then there is a heuristic with the same performance guarantee ae for MINVC. Moreover, we show that this result holds even for MINSAT instances defined by Horn formulas. It has been conjectured in [12] that no polynomial approximation algorithm can provide a performance guarantee of 2 \Gamma ffl for any fixed ffl ? 0 for MINVC unless P = NP. Thus, our result provides an indication of the difficulty involved in devising a heuristic with a performance guarantee better than 2 for MINSAT.
Spanning Trees %2D Short or Small.
We study the problem of finding small trees. Classical network design problems are considered with the additional constraint that only a specified number k of nodes are required to be connected in the solution. A prototypical example is the kMST problem in which we require a tree of minimum weight spanning at least k nodes in an edge-weighted graph. We show that the kMST problem is NP-hard even for points in the Euclidean plane. We provide approximation algorithms with performance ratio 2 p k for the general edge-weighted case and O(k 1=4 ) for the case of points in the plane. Polynomial-time exact solutions are also presented for the class of treewidth-bounded graphs which includes trees, series-parallel graphs, and bounded bandwidth graphs, and for points on the boundary of a convex region in the Euclidean plane. We also investigate the problem of finding short trees, and more generally, that of finding networks with minimum diameter. A simple technique is used to prov...
Compact Location Problems with Budget and Communication Constraints.
. We consider the problem of placing a specified number p of facilities on the nodes of a given network with two nonnegative edge-- weight functions so as to minimize the diameter of the placement with respect to the first weight function subject to a diameter-- or sum-- constraint with respect to the second weight function. Define an (ff; fi)--approximation algorithm as a polynomial--time algorithm that produces a solution within ff times the optimal value with respect to the first weight function, violating the constraint with respect to the second weight function by a factor of at most fi.  We show that in general obtaining an (ff; fi)--approximation for any fixed  ff; fi  1 is NP--hard for any of these problems. We also present efficient approximation algorithms for several of the problems studied, when both edge--weight functions obey the triangle inequality. 1 Introduction and Basic Definitions  Several fundamental problems in location theory [HM79, MF90] involve finding a placem...
Bicriteria Network Design Problems.
We study a general class of bicriteria network design problems. A generic problem in this  class is as follows: Given an undirected graph and two minimization objectives (under different  cost functions), with a budget specified on the first, find a subgraph from a given subgraph-class  that minimizes the second objective subject to the budget on the first. We consider three different  criteria - the total edge cost, the diameter and the maximum degree of the network. Here, we  present the first polynomial-time approximation algorithms for a large class of bicriteria network  design problems for the above mentioned criteria. The following general types of results are  presented.  First, we develop a framework for bicriteria problems and their approximations. Second,  when the two criteria are the same we present a &#034;black box&#034; parametric search technique. This  black box takes in as input an (approximation) algorithm for the unicriterion situation and generates  an approximation algorit...
Active Client Primary%2DBackup Protocols %28Abstract%29.

Complexity and Approximability of Certain Bicriteria Location Problems.
We investigate the complexity and approximability of some location problems when two distance values are specified for each pair of potential sites. These problems involve the selection of a specified number of facilities (i.e. a placement of a specified size) to minimize a function of one distance metric subject to a budget constraint on the other distance metric. Such problems arise in several application areas including statistical clustering, pattern recognition and load--balancing in distributed systems. We show that, in general, obtaining placements that are near-optimal with respect to the first distance metric is NP-hard even when we allow the budget constraint on the second distance metric to be violated by a constant factor. However, when both the distance metrics satisfy the triangle inequality, we present approximation algorithms that produce placements which are near-optimal with respect to the first distance metric while violating the budget constraint only by a smal...
Approximation Schemes Using L%2DReductions.

A Unified Approach to Approximation Schemes for NP%2D and PSPACE%2DHard Problems for Geometric Graphs.

Approximation Schemes Using L%2DReductions.

Spanning Trees Short or Small.
We study the problem of finding small trees. Classical network design problems are considered with the additional constraint that only a specified number k of nodes are required to be connected in the solution. A prototypical example is the kMST problem in which we require a tree of minimum weight spanning at least k nodes in an edge-weighted graph. We show that the kMST problem is NP-hard even for points in the Euclidean plane. We provide approximation algorithms with performance ratio 2 p k for the general edge-weighted case and O(k 1=4 ) for the case of points in the plane. Polynomial-time exact solutions are also presented for the class of treewidth-bounded graphs which includes trees, series-parallel graphs, and bounded bandwidth graphs, and for points on the boundary of a convex region in the Euclidean plane. We also investigate the problem of finding short trees, and more generally, that of finding networks with minimum diameter. A simple technique is used to prov...
Rectilinear Steiner Tree Heuristics and Minimum Spanning Tree Algorithms Using Geographic Nearest Neighbors.

Construction of Check Sets for Algorithm%2DBased Fault Tolerance.

Compact Location Problems.
We consider the problem of placing a specified number (p) of facilities on the nodes  of a network so as to minimize some measure of the distances between facilities. This  type of problem models a number of problems arising in facility location, statistical clustering,  pattern recognition, and processor allocation problems in multiprocessor systems.  We consider the problem under three different objectives, namely minimizing the diameter,  minimizing the average distance, and minimizing the variance. We observe that in  general, the problem is NP-hard under any of the objectives. Further, even obtaining a  constant factor approximation for any of the objectives is NP-hard.  We present a general framework for obtaining near-optimal solutions to the compact  location problems for the above measures, when the distances satisfy the triangle  inequality. We show that this framework can be extended to the case when there are  also node weights. Further, we investigate the complexity and ap...
The Complexity of Approximation PSPACE%2DComplete Problems for Hierarchical Specifications.

Compact Location Problems.
We consider the problem of placing a specified number (p) of facilities on the nodes  of a network so as to minimize some measure of the distances between facilities. This  type of problem models a number of problems arising in facility location, statistical clustering,  pattern recognition, and processor allocation problems in multiprocessor systems.  We consider the problem under three different objectives, namely minimizing the diameter,  minimizing the average distance, and minimizing the variance. We observe that in  general, the problem is NP-hard under any of the objectives. Further, even obtaining a  constant factor approximation for any of the objectives is NP-hard.  We present a general framework for obtaining near-optimal solutions to the compact  location problems for the above measures, when the distances satisfy the triangle  inequality. We show that this framework can be extended to the case when there are  also node weights. Further, we investigate the complexity and ap...
Exploiting Data Flow Information in Algorithm%2DBased Fault Tolerance.

The Complexity of Approximating PSPACE%2DComplete Problems for Hierarchical Specifications %28Extended Abstract%29.

Efficient Approximation Algorithms for Domatic Partition and On%2DLine Coloring of Circular Arc Graphs.
We exploit the close relationship between circu-lar arc graphs and interval graphs to design efficient approximation algorithms for NP-hard Optimization problems on circular arc graphs. The problems consid-ered here are maximum domatic partition and on-line minimum vertex coloring. We present a heuristic for the domatic partition problem with a performance ratio of 4. For on-line coloring, we consider two different on-line models. In the first model, arcs are presented in the increasing or-der of their left endpoints. For this model, our heuris-tic guarantees a solution which is within a factor of 2 of the optimal (off-line) value; and we show that no on-line coloring algorithm can achieve a perfor-mance guarantee of less than 3/2. In the second on-line model, arcs are presented in an arbitrary order; and it is known that no on-lane coloring algorithm can achieve a performance guarantee of less than 3. For this model, we present a heuristic which provides a performance guarantee of 4. 
Many birds with one stone multi%2Dobjective approximation algorithms.
We study network-design problems with multiple design objectives. In particular, we look at  two cost measures to be minimized simultaneously: the total cost of the network and the maximum  degree of any node in the network. Our main result can be roughly stated as follows: given an  integer b, we present approximation algorithms for a variety of network-design problems on an n-  node graph in which the degree of the output network is O(b log(  n  b )) and the cost of this network is  O(log n) times that of the minimum-cost degree-b-bounded network. These algorithms can handle  costs on nodes as well as edges. Moreover, we can construct such networks so as to satisfy a variety  of connectivity specifications including spanning trees, Steiner trees and generalized Steiner forests.  The performance guarantee on the cost of the output network is nearly best-possible unless NP = ~ P .  We also address the special case in which the costs obey the triangle inequality. In this case, we  obtai...
On Multi%2DLabel Linear Interval Routing Schemes %28Extended Abstract%29.

Improved Bounds for Algorithm%2DBased Fault Tolerance.

Graph Theoretic Analysis of PLA Folding Heuristics.

Determining Performance Measures of Algorithm%2DBased Fault Tolerant Systems.

Construction and Analysis of Fault%2DSecure Multiprocessor Schedules.

Facility Dispersion Problems Heuristics and Special Cases %28Extended Abstract%29.

Minimum area layout of series%2Dparallel transistor networks is NP%2Dhard.

Computing optimal test sequences from complete test sets for stuck%2Dopen faults in CMOS circuits.

Journal backlog report.

On the orderability problem for PLA folding.

The Complexity of Generating Minimum Test Sets for PLA%27s and Monotone Combinational Circuits.

An O%28n log n%29 Lower Bound for Decomposing a Set of Points into Chains.

On approximation algorithms for microcode bit minimization.

The Complexity of Near%2DOptimal Programmable Logic Array Folding.

An Application of the Planar Separator Theorem to Counting Problems.

One%2DLayer Routing without Component Constraints.

